#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

#define MAXWORD 100

struct tnode { /* the tree node: */
    char *word; /* points to the text */
    int count; /* number of occurrences */
    struct tnode *left; /* left child */
    struct tnode *right; /* right child */
};

struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);

/* word frequency count */
int main()
{
    struct tnode *root;
    char word[MAXWORD];

    root = NULL;
    while (getword(word, MAXWORD) != EOF)
        if (isalpha(word[0]))
            root = addtree(root, word);

    treeprint(root);

    return 0;
}

struct tnode *talloc(void);
char *strdup_my(char *);


/* 请在这里填写答案 */
struct tnode *talloc(void)
{
    struct tnode * node=malloc(sizeof(struct tnode));
    node->left=NULL;
    node->right=NULL;
    node->word=NULL;
    node->count=0;
    return node;
}
char *strdup_my(char *s)
{
    int l=strlen(s);
    char * ans=malloc(l+1);
    strcpy(ans,s);
    return ans;
}
struct tnode *addtree(struct tnode * node, char *word)
{
    if(node)
    {
        int res=strcmp(word,node->word);
        if(res==0)      ++node->count;
        else if(res<0)    node->left=addtree(node->left,word);
        else              node->right=addtree(node->right,word);
    }
    else
    {
        node=talloc();
        ++node->count;
        node->word=strdup_my(word);
    }
    return node;
}
void treeprint(struct tnode *node)
{
    if(node)
    {
        treeprint(node->left);
        printf("%d %s\n",node->count,node->word);
        treeprint(node->right);
    }
}



int getch(void);
void ungetch(int);

/* getword: get next word or character from input */
int getword(char *word, int lim)
{
    int c;
    char *w = word;

    while (isspace(c = getch()))
        ;

    if (c != EOF)
        *w++ = c;

    if (!isalpha(c)) {
        *w = '\0';
        return c;
    }

    for ( ; --lim > 0; w++)
        if (!isalnum(*w = getch())) {
            ungetch(*w);
            break;
        }

    *w = '\0';

    return word[0];
}


#define BUFSIZE 100

char buf[BUFSIZE]; /* buffer for ungetch */
int bufp = 0; /* next free position in buf */

/* get a (possibly pushed-back) character */
int getch(void)
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}

/* push character back on input */
void ungetch(int c)
{
    if (bufp >= BUFSIZE)
        printf("ungetch: too many characters\n");
    else
        buf[bufp++] = c;
}